Sağdan
sola və soldan sağa eyni cür oxunan sətirlərə
palindrom deyilir. Superpolindrom isə bir neçə Palindromun
konkatenasiyasından alınan sətirlər hesab olunur. S sətri verilir. S-in superpalindrom olan alt sətirlərinin
sayını tapmaq tələb olunur
Giriş. S sətri 1-dən 1000-ə qədər
kiçik latın hərflərindən ibarət probelsiz ardıcıllıqdır.
Çıxış. Çıxışa
bir ədəd S-in superpalindrom olan alt sətirlərinin sayı
verilir.
Girişə nümunə
abacdc
Çıxışa
nümunə
3
dinamik proqramlama - palindromlar
Tutaq ki, S
giriş sətridir. O zaman si…sj palindromdursa, dp[i][j] = 1, digər halda isə dp[i][j] = 0 olsun.
0 ≤ i < j < n
üçün bütün elə
(i, j) cütlərini
seçək ki, si…sj palindrom olsun, onda o həm də superpolindromdur və dp[i][j]
= 1.
Hər bir (i, j)
cütü üçün bütün mümkün k (i
< k < j – 1) ədədləri
seçək ki, si…sk və sk+1…sj superpolindrom olsun (onlar k ilə
məhtudlandıği üçün elementəri 1-dən
çox olar), onda si…sj -də superpolindromdur.
İndi yalnız dp[i][j] = 1, olan (i, j)
cütlərini saymaq qalır ki, bu ədəd də cavab
olar.
İşçi
massivlər:
#define MAX 1010
char s[MAX];
int dp[MAX][MAX];
int pal[MAX][MAX];
int IsPal(int
i, int j)
{
if (i >=
j) return pal[i][j] = 1;
if (pal[i][j]
!= -1) return pal[i][j];
return
pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);
}
Proqramın
əsas hissəsi. Giriş sətrini oxuyuruq.
gets(s); n =
strlen(s);
memset(dp,0,sizeof(dp));
memset(pal,-1,sizeof(pal));
İnterval uzunluqlarının artma
ardıcıllığına görə bütün (i, i + len) cütlərini seçirik.
for(len = 1; len < n; len++)
for(i = 0; i + len < n; i++)
{
j = i + len;
Ïîäñòðîêà
si…sj -alt sətri birdən çox
elementə malikdir və o paindromdursa demək o həm də
superpolindromdur.
if
(IsPal(i,j))
{
dp[i][j] = 1;
continue;
}
Əgər si…sk və sk+1…sj superpolindromdursa
onda si…sj də
superpalindromdur.
for(k = i +
1; k < j - 1; k++)
if(dp[i][k]
&& dp[k + 1][j])
{
dp[i][j] = 1;
break;
}
}
Superpalindrom
cütlərini sayırıq
res = 0;
for(i = 0; i < n; i++)
for(j = 1; j < n; j ++)
res += dp[i][j];
Cavabı çıxarırıq.
printf("%d\n",res);